/*
 * Copyright (c) 2024 iSOFT INFRASTRUCTURE SOFTWARE CO., LTD.
 * easyAda is licensed under Mulan PubL v2.
 * You can use this software according to the terms and conditions of the Mulan PubL v2.
 * You may obtain a copy of Mulan PubL v2 at:
 *          http://license.coscl.org.cn/MulanPubL-2.0
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PubL v2 for more details.
 */

#ifndef RBTREE_H
#define RBTREE_H

#include <stdlib/limits.h>

typedef struct rbnode {
    struct rbnode *parent;
    struct rbnode *lchild, *rchild;
    unsigned long  data : (WORD_BITS - 1);
    unsigned       color : 1;
} rbnode_t;

void rbtree_insert(rbnode_t *tree, rbnode_t *node, int (*compare_less)(rbnode_t *lhs, rbnode_t *rhs));

void rbtree_delete(rbnode_t *tree, rbnode_t *node);

rbnode_t *rbtree_find(const rbnode_t *tree, unsigned long data, int (*compare)(rbnode_t *lhs, unsigned long data));

rbnode_t *rbtree_left_most(const rbnode_t *tree);

rbnode_t *rbnode_next(const rbnode_t *tree, const rbnode_t *node);

void rbtree_head_init(rbnode_t *head);

#ifdef RBTREE_TEST_TOOL

int tree_check(rbnode_t *tree, int *depth, int *nodes);
#endif

#endif
